package code1701_1800.code1_10;

import java.util.*;

/**
 * 有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。在第 i 天，树上会长出 apples[i] 个苹果，
 * 这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，
 * 此时用 apples[i] == 0 且 days[i] == 0 表示。
 *
 * 你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 n 天之后继续吃苹果。
 *
 * 给你两个长度为 n 的整数数组 days 和 apples ，返回你可以吃掉的苹果的最大数目。
 *
 * 输入：apples = [1,2,3,5,2], days = [3,2,1,4,2]
 * 输出：7
 * 解释：你可以吃掉 7 个苹果：
 * - 第一天，你吃掉第一天长出来的苹果。
 * - 第二天，你吃掉一个第二天长出来的苹果。
 * - 第三天，你吃掉一个第二天长出来的苹果。过了这一天，第三天长出来的苹果就已经腐烂了。
 * - 第四天到第七天，你吃的都是第四天长出来的苹果。
 *
 * 输入：apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
 * 输出：5
 * 解释：你可以吃掉 5 个苹果：
 * - 第一天到第三天，你吃的都是第一天长出来的苹果。
 * - 第四天和第五天不吃苹果。
 * - 第六天和第七天，你吃的都是第六天长出来的苹果。
 *
 */
public class _1705eatenApples {

    /**
     * 没做出来
     * @param apples
     * @param days
     * @return
     */
    public int eatenApples0(int[] apples, int[] days) {
        // 经过测试，苹果总数和腐烂时间必须用数组数据结构存储。此时用map好一点
        List<int[]> appleNum = new ArrayList<>();
        int result = 0;
        int day;
        int num;
        for (int i = 0; i < apples.length; i++) {
            // 这一天有新苹果产生，则加入到苹果总数
            if(days[i]>1&&apples[i]>0){
                appleNum.add(new int[]{i,apples[i]});
            }
            // 这一天有苹果腐烂，则去掉。如果还有苹果就吃掉
            for (int j = 0; j < appleNum.size(); j++) {
                // 当天的苹果还剩下几个
                day = i - appleNum.get(j)[0];
                num = appleNum.get(j)[1];
                if(day > 0&& num>0){
                    appleNum.get(j)[0]--;
                    appleNum.get(j)[1]--;
                    ++result;
                }else {
                    appleNum.get(j)[1] = 0;
                }
            }
        }
        for (int i = 0; i < appleNum.size(); i++) {
            day = appleNum.get(i)[0];
            num = appleNum.get(i)[1];
            if(num>0&&day>0){
                if(num>day){
                    result+=day;
                    appleNum.get(i)[0] = 0;
                    appleNum.get(i)[1] = 0;
                }else {
                    result+=num;
                    appleNum.get(i)[0] = 0;
                    appleNum.get(i)[1] = 0;
                }
            }
        }
        return result;
    }

    /**
     * 贪心+优先队列
     * @param apples
     * @param days
     * @return
     */
    public int eatenApples(int[] apples, int[] days) {
        int ans = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[0]-b[0]);
        int n = apples.length;
        int i = 0;
        while (i<n){
            while (!pq.isEmpty()&&pq.peek()[0]<=i){
                pq.poll();
            }
            int rottenDay = i+days[i];
            int count = apples[i];
            if(count>0){
                pq.offer(new int[]{rottenDay,count});
            }
            if(!pq.isEmpty()){
                int[] arr = pq.peek();
                arr[1]--;
                if(arr[1] == 0){
                    pq.poll();
                }
                ans++;
            }
            i++;
        }
        while (!pq.isEmpty()){
            while (!pq.isEmpty()&&pq.peek()[0]<=i){
                pq.poll();
            }
            if(pq.isEmpty()){
                break;
            }
            int[] arr = pq.poll();
            int curr = Math.min(arr[0]-i,arr[1]);
            ans += curr;
            i += curr;
        }
        return ans;
    }

}
